#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>

using namespace std;

// 1048. 最长字符串链
class Solution 
{
public:
    int longestStrChain(vector<string>& words) 
    {
        sort(words.begin(), words.end(), [](auto& a, auto& b){
            return a.size() < b.size();
        });

        int ans = 0;
        unordered_map<string, int> f;
        for(auto& s : words)
        {
            int ret = 0;
            for(int i = 0; i < s.size(); ++i)
            {
                auto it = f.find(s.substr(0, i) + s.substr(i + 1));
                if(it != f.end())
                {
                    ret = max(ret, it->second);
                }
            }
            ans = max(ans, f[s] = ret + 1);
        }
        return ans;
    }
};

// 2750. 将数组划分成若干好子数组的方式
class Solution 
{
public:
    int numberOfGoodSubarraySplits(vector<int>& nums) 
    {
        const int MOD = 1e9 + 7;
        int ret = 1, pre = -1, n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == 0) continue;
            if(pre >= 0) ret = (long)ret * (i - pre) % MOD;
            pre = i;
        }
        return pre < 0 ? 0 : ret;
    }
};

// 1218. 最长定差子序列
class Solution 
{
public:
    int longestSubsequence(vector<int>& arr, int diff) 
    {
        unordered_map<int, int> m;
        m[arr[0]] = 1;
        int n = arr.size(), ret = 1;
        for(int i = 1; i < n; ++i)
        {
            m[arr[i]] = m[arr[i] - diff] + 1;
            ret = max(ret, m[arr[i]]);
        }
        return ret;
    }
};

// 1247. 交换字符使得字符串相同
class Solution 
{
public:
    int minimumSwap(string s1, string s2) 
    {
        int cnt[2]{}, n = s1.size();
        for(int i = 0; i < n; ++i)
        {
            if(s1[i] != s2[i]) ++cnt[s1[i] % 2];
        }
        int d = cnt[0] + cnt[1];
        return d % 2 != 0 ? -1 : d / 2 + cnt[0] % 2;
    }
};

class Solution 
{
public:
    int differenceOfSums(int n, int m) 
    {
        int sum = n * (n + 1) / 2;
        int a = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(i % m != 0) a += i;
        }  
        return 2 * i - sum;
    }
};

class Solution {
public:
    int minProcessingTime(vector<int>& p, vector<int>& tasks) {
        sort(p.begin(), p.end());
        sort(tasks.begin(), tasks.end());
        int n = p.size(), m = tasks.size();
        int ret = INT_MIN;
        for(int i = 0; i < n; ++i)
        {
            ret = max(ret, p[i] + tasks[m - 1 - i * 4]);
        }
        return ret;
    }
};
